package com.wtgroup.demo.leetcode.q300_最长递增子序列;

import com.wtgroup.demo.common.judge.Judger;
import com.wtgroup.demo.common.util.RandomUtil;
import com.wtgroup.demo.common.util.Tools;
import org.junit.Test;

/**
 * @author dafei
 * @version 0.1
 * @date 2021/4/15 15:28
 */
public class Q300_DP {

    @Test
    public void foo1() {
        // int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};

        new Judger(() -> {
            int[] nums = RandomUtil.randomArray((int) (Math.random() * 20 + 1), 0, 30);
            int res1 = new Solution().lengthOfLIS(nums);
            // System.out.println(res1);
            // int res2 = new Solution_T2().lengthOfLIS(nums);
            int res2 = new Solution_T3().lengthOfLIS(nums);
            // System.out.println(res2);
            if (res1 != res2) {
                Tools.printArray(nums);
                System.out.println(res1);
                System.out.println(res2);
                return false;
            }
            return true;
        }).start().print();
    }

    @Test
    public void foo2() {
        int[] nums = {6, 19, 22, 5, 18, 18, 6}; // 3
        int res2 = new Solution_T().lengthOfLIS(nums);
        System.out.println(res2);
    }


    /**
     * 动态规划方式
     */
    class Solution {
        public int lengthOfLIS(int[] nums) {
            int n = nums.length;
            if (n == 0) {
                return 0;
            }

            int[] dp = new int[n];
            dp[0] = 1;
            int maxLen = dp[0];
            for (int i = 1; i < n; i++) {
                dp[i] = 1;
                for (int j = 0; j < i; j++) {
                    if (nums[j] < nums[i]) {
                        dp[i] = Math.max(dp[j] + 1, dp[i]);
                    }
                }
                if (dp[i] > maxLen) maxLen = dp[i];
            }

            return maxLen;
        }
    }


    /**
     * 每个元素为开始的子序列, 逐个尝试.
     * 失败。{16, 7, 25, 26, 27, 0, 12, 19} ， 一直认为是 0,12,19 , 得到3个.
     * <p>
     * 考察以 i 为开始的子序列, 递归里面, i 位值就是最小的基准值.
     *
     * @deprecated 尝试策略不行
     */
    class Solution_T {
        public int lengthOfLIS(int[] nums) {
            int N = nums.length;
            if (nums == null || N == 0) {
                return 0;
            }

            // 挨个位置尝试
            for (int i = 0; i < N; i++) {

            }

            return func(nums, 0, nums[0])[0] + 1;
        }

        // 当前位<后面最长子序列最小值 & > baseVal => 入序列
        int[] func(int[] nums, int index, int baseVal) {
            int n = nums.length;
            int[] res = new int[2];
            if (index == n) {
                res[0] = 0; // 0?1?
                res[1] = Integer.MAX_VALUE;
                // if (nums[n - 1] > baseVal) {
                //     res[0] = 1;
                //     res[1] = nums[n - 1];
                // } else {
                //     // 子序列长度 0
                //     res[0] = 0;
                //     res[1] = Integer.MAX_VALUE;
                // }
                return res;
            }

            int maxLen = 0;
            int minVal = Integer.MAX_VALUE;
            for (int i = index + 1; i < n; i++) {
                res = func(nums, i, baseVal);
                maxLen = Math.max(maxLen, res[0] + 1);
                minVal = Math.min(minVal, res[1]);
            }

            // if (nums[index] > baseVal && nums[index] < res[1]) {
            //     res[0] += 1;
            //     res[1] = nums[index];
            // } // else 不入, 后面子序列结果透返

            return res;
        }
    }

    /**
     *
     */
    class Solution_T2 {
        public int lengthOfLIS(int[] nums) {
            int N = nums.length;
            int ans = 0;
            for (int i = 0; i < N; i++) {
                // 以 i 位置结尾的最长子序列长度
                int r = func(nums, i);
                ans = Math.max(ans, r);
            }

            return ans;
        }

        // index 位置结尾的最大子序列长度
        // 0...index-1 同质子问题得到后, 取最大的
        private int func(int[] nums, int index) {
            if (index==0) {
                return 1;
            }

            int res = 1;
            // index 依赖 0,1,...,index-1
            for (int i = 0; i < index; i++) {
                // 函数语义要求 i 结尾的, 那么, i值>index值, 忽略
                if (nums[i] < nums[index]) {
                    res = Math.max(res, func(nums, i) + 1);
                }
            }
            return res;
        }

    }

    // 暴力递归-->动态规划
    class Solution_T3 {

        public int lengthOfLIS(int[] nums) {
            int N = nums.length;
            // 一个可变参数, 一维dp
            int[] dp = new int[N];
            for (int i = 0; i < N; i++) {
                dp[i] = 1;
            }

            int ans = 1;
            for (int index = 0; index < N; index++) {
                // 以 i 位置结尾的最长子序列长度
                // int r = func(nums, i);
                for (int j = 0; j < index; j++) {
                    // 函数语义要求 i 结尾的, 那么, i值>index值, 忽略
                    if (nums[j] < nums[index]) {
                        dp[index] = Math.max(dp[index], dp[j] + 1);
                    }
                }

                ans = Math.max(ans, dp[index]);
            }

            return ans;
        }
    }

}
